import java.util.*;


public class Solution {
    private PriorityQueue<Integer> heap = new PriorityQueue<>();
    List<Integer> tmp = new ArrayList<>();

    public void Insert(Integer num) {
        heap.add(num);
    }

    public Double GetMedian() {
        double ret = 0.0;
        int n = heap.size();
        if (n % 2 == 0) {// 说明是偶数个
            while (heap.size() > n / 2) {
                tmp.add(heap.remove());
            }
            if (!heap.isEmpty()) {
                ret = (double) (heap.peek() + tmp.get(tmp.size() - 1)) / 2;
            }
            while (!tmp.isEmpty()) {
                heap.add(tmp.remove(0));
            }
        } else {// 说明是奇数个
            while (heap.size() > (n + 1) / 2) {
                tmp.add(heap.remove());
            }
            if (!heap.isEmpty()) {
                ret = heap.peek();
            }
            while (!tmp.isEmpty()) {
                heap.add(tmp.remove(0));
            }
        }


        return ret;
    }


}
